Introduction

In this report, we will be doing a Principal Component analysis based on Spotify data on popular songs.

A Principal Component Analysis is a technique to analyze large datasets containing multiple dimensions/features. The purpose is to enable visualization of multidimensional data.

PCA identifies the main axes of variance within a data set and allows for easy data exploration to understand the key variables in the data and spot outliers.

The goal is to determine which variables are related or not related to each other.

library(tidyverse)
library(janitor)

Importing the data

We are using a dataset of popular songs on Spotify. In the previous report on pre-processing, descriptive and bivariate statistics, we have described this dataset and made several transformations.

Link to original dataset

setwd("~/Documents/class/stats-final-project/")
Warning: The working directory was changed to /Users/sadeline/Documents/class/stats-final-project inside a notebook chunk. The working directory will be reset when the chunk is finished running. Use the knitr root.dir option in the setup chunk to change the working directory for notebook chunks.
dd <- read.csv("cleaneddata.csv")

Performing the Principal Component Analysis

We use the prcomp() function.

This returns 3 things:

  1. x => contains the principal components (PCs) for drawing a graph. We will be using the first two columns in x to draw a 2D plot that uses the first 2 PCs. The number of PCs is determined by the number of variables used.

  2. sdev

  3. rotation

Below is the code to run the prcomp function, and a basic plot of principal component 1 and 2.

# determine which ones are numerical variables
numerical <- which(sapply(dd,is.numeric))
# print below to see if the numerical variables are correctly detected
# numerical

# saving the numerical observations to "dcon"
dcon <- dd[,numerical]
# print below to see if variables detected are indeed numerical
# sapply(dcon,class)

# Now we do a PRINCIPAL COMPONENT ANALYSIS on the numerical variables
pca <- prcomp(dcon, scale=TRUE, center = TRUE) # centering and scaling true
pc1 <- pca

plot(pca$x[,1], pca$x[,2])

Scree plot

With the principal component analysis, we can also compute the Scree plot, which displays the variance accounted for by the components.

pca.var <- pca$sdev^2
pca.var.per <- round(pca.var/sum(pca.var)*100, 1)
pca.var.per
 [1] 25.2 13.1 11.0  9.8  8.2  7.3  6.6  6.3  5.5  3.3  2.7  1.1
barplot(pca.var.per, main="Scree Plot", xlab="Principal Component", ylab="Percent Variation")


#Cummulated Inertia in subspaces, from first principal component to the 11th dimension subspace
barplot(100*cumsum(pc1$sdev[1:dim(dcon)[2]]^2)/dim(dcon)[2])

percInerAccum<-100*cumsum(pc1$sdev[1:dim(dcon)[2]]^2)/dim(dcon)[2]
percInerAccum
 [1]  25.18941  38.27479  49.25786  59.02753  67.26210  74.52773  81.08438  87.38892  92.85235  96.13973
[11]  98.85433 100.00000

From this we see that Principal component 1 accounts for only 25.2% of the variation. And in order to account for 80% of the variation, we need to include PC 1-7.

Next we will store the eigenvalues, eigenvectors, projections and include PC 1-7.

# SELECTION OF THE SINGIFICANT DIMENSIONS (keep 80% of total inertia)
nd = 7
pc1$rotation
# STORAGE OF THE EIGENVALUES, EIGENVECTORS AND PROJECTIONS IN THE nd DIMENSIONS
Psi = pc1$x[,1:nd]
Psi
# STORAGE OF LABELS FOR INDIVIDUALS AND VARIABLES
iden = row.names(dcon)
etiq = names(dcon) # getting names of numerical variables
ze = rep(0,length(etiq)) # WE WILL NEED THIS VECTOR AFTERWARDS FOR THE GRAPHICS

Plotting the individuals on PC1 and PC2 axes

# PLOT OF INDIVIDUALS

#select your axis
#eje1<-2
eje1<-1
#eje2<-3
eje2<-2

plot(Psi[,eje1],Psi[,eje2])
text(Psi[,eje1],Psi[,eje2],labels=iden, cex=0.5)
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")

Plotting projection of variables, PC1 and PC2

We will create a loadings plot to see which variables most influence PC1 and PC2.

#Projection of variables

Phi = cor(dcon,Psi)
Phi
                         PC1         PC2         PC3         PC4         PC5          PC6         PC7
popularity       -0.24963532  0.08737373  0.06928732 -0.76486554  0.19582865  0.022250675  0.13691622
duration_ms      -0.09862125  0.57086629 -0.24944613  0.08729430  0.41867774 -0.015558089  0.59669195
danceability     -0.40179818 -0.59488199 -0.35184714  0.25033708  0.12847324 -0.109087549  0.29817715
energy           -0.84361522  0.30812067  0.10770418  0.19022208 -0.09452873 -0.124664432 -0.12816114
loudness         -0.86472495  0.08594352  0.05548540 -0.07341474 -0.10423578 -0.146350079 -0.09242656
speechiness      -0.12184739 -0.19649985  0.58525297  0.45771434  0.08763029  0.193391954  0.20368192
acousticness      0.70188772 -0.44726772  0.12371687 -0.19446711  0.07742870  0.206281277  0.12109473
instrumentalness  0.52724351  0.33062244 -0.24448643  0.46281173 -0.05225130  0.021319812 -0.07477844
liveness         -0.16028913  0.07616872  0.75382525  0.04841263  0.23748555  0.108454828  0.04399959
valence          -0.54570179 -0.62066253 -0.14382045  0.03690987 -0.08294104 -0.007140834  0.12850532
tempo            -0.36049724  0.18146229 -0.17543765 -0.04986269 -0.43193432  0.765021423  0.14563189
time_signature   -0.30147566 -0.09267949 -0.27414163  0.08815102  0.68698749  0.380526932 -0.44354561
X<-Phi[,eje1]
Y<-Phi[,eje2]

#zooms
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(min(X,0),max(X,0)), ylim=c(-1,1))
axis(side=1, pos= 0, labels = F)
axis(side=3, pos= 0, labels = F)
axis(side=2, pos= 0, labels = F)
axis(side=4, pos= 0, labels = F)
arrows(ze, ze, X, Y, length = 0.07,col="blue")
text(X,Y,labels=etiq,col="darkblue", cex=0.7)

Observations:

Based on the Loadings plot, we see that the variables that most influence PC1 are instrumentalness, energy, loudness, and acousticness.

The variables that most influence PC2 are duration.

From this plot we can also see that these variables may be positively correlated: - Loudness and energy - Valence and danceability - Instrumentalness and acousticness

These variables may be negatively correlated: - Loudness and instrumentalness - Loudness and acousticness - Energy and acousticness - Valence and instrumentalness - Tempo and acousticness

We can also try plotting the PC1 against PC3 to see the variables that are not so clearly visible here.

Plotting projection of variables, PC1 and PC3

Since PC1 and PC2 only accounts for 38% of the variation, we should also plot projection of variables in PC1 and PC3.

#Projection of variables

Phi = cor(dcon,Psi)
Phi
                         PC1         PC2         PC3         PC4         PC5          PC6         PC7
popularity       -0.24963532  0.08737373  0.06928732 -0.76486554  0.19582865  0.022250675  0.13691622
duration_ms      -0.09862125  0.57086629 -0.24944613  0.08729430  0.41867774 -0.015558089  0.59669195
danceability     -0.40179818 -0.59488199 -0.35184714  0.25033708  0.12847324 -0.109087549  0.29817715
energy           -0.84361522  0.30812067  0.10770418  0.19022208 -0.09452873 -0.124664432 -0.12816114
loudness         -0.86472495  0.08594352  0.05548540 -0.07341474 -0.10423578 -0.146350079 -0.09242656
speechiness      -0.12184739 -0.19649985  0.58525297  0.45771434  0.08763029  0.193391954  0.20368192
acousticness      0.70188772 -0.44726772  0.12371687 -0.19446711  0.07742870  0.206281277  0.12109473
instrumentalness  0.52724351  0.33062244 -0.24448643  0.46281173 -0.05225130  0.021319812 -0.07477844
liveness         -0.16028913  0.07616872  0.75382525  0.04841263  0.23748555  0.108454828  0.04399959
valence          -0.54570179 -0.62066253 -0.14382045  0.03690987 -0.08294104 -0.007140834  0.12850532
tempo            -0.36049724  0.18146229 -0.17543765 -0.04986269 -0.43193432  0.765021423  0.14563189
time_signature   -0.30147566 -0.09267949 -0.27414163  0.08815102  0.68698749  0.380526932 -0.44354561
eje3 <- 3

X<-Phi[,eje1]
Y<-Phi[,eje3]

#zooms
plot(Psi[,eje1],Psi[,eje3],type="n",xlim=c(min(X,0),max(X,0)), ylim=c(-1,1))
axis(side=1, pos= 0, labels = F)
axis(side=3, pos= 0, labels = F)
axis(side=2, pos= 0, labels = F)
axis(side=4, pos= 0, labels = F)
arrows(ze, ze, X, Y, length = 0.07,col="blue")
text(X,Y,labels=etiq,col="darkblue", cex=0.7)

Based on the above Loadings plot, we see that the variables that most influence PC3 are popularity, liveness and duration.

It also seems like Popularity and liveness are closely related, while it may be negatively correlated with duration.

We can also see that speechiness is closer to danceability.

Finding Centroids

We can also find the centroids of modalities in categorical variables, using the code below.


X<-Phi[,eje1]
Y<-Phi[,eje2]

plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,1), ylim=c(-3,1))
#plot(X,Y,type="none",xlim=c(min(X,0),max(X,0)))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")

arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)


#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-2,4), ylim=c(-2,2))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)

#nominal qualitative variables

dcat<-c(3, 6, 8, 16, 17)
colors<-rainbow(length(dcat))

c<-1
for(k in dcat){
  seguentColor<-colors[c]
fdic1 = tapply(Psi[,eje1],dd[,k],mean)
fdic2 = tapply(Psi[,eje2],dd[,k],mean) 

text(fdic1,fdic2,labels=levels(factor(dd[,k])),col=seguentColor, cex=0.6)
c<-c+1
}
legend("bottomleft",names(dd)[dcat],pch=1,col=colors, cex=0.6)

#add ordinal qualitative variables. Ensure ordering is the correct

dordi<-c(18)


#reorder modalities: when required
dd[,dordi[1]] <- factor(dd[,dordi[1]], ordered=TRUE,  levels= c('Larghissimo','Grave','Lento/Largo','Larghetto','Adagio','Andante','Moderato','Allegro','Vivace','Presto','Prestissimo'))
levels(dd[,dordi[1]])
 [1] "Larghissimo" "Grave"       "Lento/Largo" "Larghetto"   "Adagio"      "Andante"     "Moderato"   
 [8] "Allegro"     "Vivace"      "Presto"      "Prestissimo"
c<-1
col<-length(dcat)+1
for(k in dordi){
  seguentColor<-colors[col]
  fdic1 = tapply(Psi[,eje1],dd[,k],mean)
  fdic2 = tapply(Psi[,eje2],dd[,k],mean) 
  
  #points(fdic1,fdic2,pch=16,col=seguentColor, labels=levels(dd[,k]))
  #connect modalities of qualitative variables
  lines(fdic1,fdic2,col="#000000")
  text(fdic1,fdic2,labels=levels(dd[,k]),col=seguentColor, cex=0.6)
  c<-c+1
  col<-col+1
}
legend("topleft",names(dd)[dordi],pch=19,col=colors[col:col+length(dordi)-1], cex=0.6)

That looks a bit crowded, so let’s try looking at the modalities one by one.

Explicit

#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,1), ylim=c(-1,1))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)

#nominal qualitative variables

dcat<-c(3)
colors<-rainbow(length(dcat))

c<-1
for(k in dcat){
  seguentColor<-colors[c]
fdic1 = tapply(Psi[,eje1],dd[,k],mean)
fdic2 = tapply(Psi[,eje2],dd[,k],mean) 

text(fdic1,fdic2,labels=levels(factor(dd[,k])),col=seguentColor, cex=0.6)
c<-c+1
}
legend("bottomleft",names(dd)[dcat],pch=1,col=colors, cex=0.6)

NA
NA

Key

#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,1), ylim=c(-1,1))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)

#nominal qualitative variables

dcat<-c(6)
colors<-rainbow(length(dcat))

c<-1
for(k in dcat){
  seguentColor<-colors[c]
fdic1 = tapply(Psi[,eje1],dd[,k],mean)
fdic2 = tapply(Psi[,eje2],dd[,k],mean) 

text(fdic1,fdic2,labels=levels(factor(dd[,k])),col=seguentColor, cex=0.6)
c<-c+1
}
legend("bottomleft",names(dd)[dcat],pch=1,col=colors, cex=0.6)

NA
NA

Mode

#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,1), ylim=c(-1,1))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)

#nominal qualitative variables

dcat<-c(8)
colors<-rainbow(length(dcat))

c<-1
for(k in dcat){
  seguentColor<-colors[c]
fdic1 = tapply(Psi[,eje1],dd[,k],mean)
fdic2 = tapply(Psi[,eje2],dd[,k],mean) 

text(fdic1,fdic2,labels=levels(factor(dd[,k])),col=seguentColor, cex=0.6)
c<-c+1
}
legend("bottomleft",names(dd)[dcat],pch=1,col=colors, cex=0.6)

NA
NA

Multiple artists

#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,3), ylim=c(-2,2))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)

#nominal qualitative variables

dcat<-c(17)
colors<-rainbow(length(dcat))

c<-1
for(k in dcat){
  seguentColor<-colors[c]
fdic1 = tapply(Psi[,eje1],dd[,k],mean)
fdic2 = tapply(Psi[,eje2],dd[,k],mean) 

text(fdic1,fdic2,labels=levels(factor(dd[,k])),col=seguentColor, cex=0.6)
c<-c+1
}
legend("bottomleft",names(dd)[dcat],pch=1,col=colors, cex=0.6)

NA
NA

All except genre


#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,3), ylim=c(-2,2))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)

#nominal qualitative variables

dcat<-c(3,6,8,17)
colors<-rainbow(length(dcat))

c<-1
for(k in dcat){
  seguentColor<-colors[c]
fdic1 = tapply(Psi[,eje1],dd[,k],mean)
fdic2 = tapply(Psi[,eje2],dd[,k],mean) 

text(fdic1,fdic2,labels=levels(factor(dd[,k])),col=seguentColor, cex=0.6)
c<-c+1
}
legend("bottomleft",names(dd)[dcat],pch=1,col=colors, cex=0.6)



#add ordinal qualitative variables. Ensure ordering is the correct

dordi<-c(18)


#reorder modalities: when required
dd[,dordi[1]] <- factor(dd[,dordi[1]], ordered=TRUE,  levels= c('Larghissimo','Grave','Lento/Largo','Larghetto','Adagio','Andante','Moderato','Allegro','Vivace','Presto','Prestissimo'))
levels(dd[,dordi[1]])
 [1] "Larghissimo" "Grave"       "Lento/Largo" "Larghetto"   "Adagio"      "Andante"     "Moderato"   
 [8] "Allegro"     "Vivace"      "Presto"      "Prestissimo"
c<-1
col<-length(dcat)+1
for(k in dordi){
  seguentColor<-colors[col]
  fdic1 = tapply(Psi[,eje1],dd[,k],mean)
  fdic2 = tapply(Psi[,eje2],dd[,k],mean) 
  
  #points(fdic1,fdic2,pch=16,col=seguentColor, labels=levels(dd[,k]))
  #connect modalities of qualitative variables
  lines(fdic1,fdic2,col="#000000")
  text(fdic1,fdic2,labels=levels(dd[,k]),col=seguentColor, cex=0.6)
  c<-c+1
  col<-col+1
}
legend("topleft",names(dd)[dordi],pch=19,col=colors[col:col+length(dordi)-1], cex=0.6)

NA
NA

#all qualitative together
plot(Psi[,eje1],Psi[,eje2],type="n",xlim=c(-1,3), ylim=c(-1,1))
axis(side=1, pos= 0, labels = F, col="cyan")
axis(side=3, pos= 0, labels = F, col="cyan")
axis(side=2, pos= 0, labels = F, col="cyan")
axis(side=4, pos= 0, labels = F, col="cyan")
arrows(ze, ze, X, Y, length = 0.07,col="lightgray")
text(X,Y,labels=etiq,col="gray", cex=0.7)


#add ordinal qualitative variables. Ensure ordering is the correct

dordi<-c(18)


#reorder modalities: when required
dd[,dordi[1]] <- factor(dd[,dordi[1]], ordered=TRUE,  levels= c('Larghissimo','Grave','Lento/Largo','Larghetto','Adagio','Andante','Moderato','Allegro','Vivace','Presto','Prestissimo'))
levels(dd[,dordi[1]])
 [1] "Larghissimo" "Grave"       "Lento/Largo" "Larghetto"   "Adagio"      "Andante"     "Moderato"   
 [8] "Allegro"     "Vivace"      "Presto"      "Prestissimo"
c<-1
col<-length(dcat)+1
for(k in dordi){
  seguentColor<-colors[col]
  fdic1 = tapply(Psi[,eje1],dd[,k],mean)
  fdic2 = tapply(Psi[,eje2],dd[,k],mean) 
  
  #points(fdic1,fdic2,pch=16,col=seguentColor, labels=levels(dd[,k]))
  #connect modalities of qualitative variables
  lines(fdic1,fdic2,col="#000000")
  text(fdic1,fdic2,labels=levels(dd[,k]),col=seguentColor, cex=0.6)
  c<-c+1
  col<-col+1
}
legend("topleft",names(dd)[dordi],pch=19,col=colors[col:col+length(dordi)-1], cex=0.6)

NA
NA

Observations from the plot of centroids above:

  1. Songs that are explicit are closely related to heavy metal and grunge songs.
  2. Disney, jazz, and classical-tonk songs are probably high on the instrumental scale, while new-age, ambient, sleep songs are high on the acousticness scale.
  3. Seems like the slower songs (Grave, Lento, Larghetto, Adagio) are also on the right side of the plot, which are more acoustic, instrumental songs. Whereas the faster songs are on the left side.

Coloring the PCA plot using categorical variables

We can also plot all the individuals in PC1 and PC2 as axes, and color-code it by categorical variables. We’ll examine one categorical variable: Explicitness


# PROJECTION OF ILLUSTRATIVE qualitative variables on individuals' map
varcat=factor(dd[,3])
plot(Psi[,1],Psi[,2],col=c("grey", "red")[varcat])
axis(side=1, pos= 0, labels = F, col="darkgray")
axis(side=3, pos= 0, labels = F, col="darkgray")
axis(side=2, pos= 0, labels = F, col="darkgray")
axis(side=4, pos= 0, labels = F, col="darkgray")
legend("bottomleft",levels(varcat),pch=1,col=c("grey", "red"), cex=0.6)


# Overproject THE CDG OF  LEVELS OF varcat
fdic1 = tapply(Psi[,1],varcat,mean)
fdic2 = tapply(Psi[,2],varcat,mean) 

text(fdic1,fdic2,labels=levels(factor(varcat)),col="cyan", cex=0.75)

Although there are not many explicit songs, we can see that the explicit songs tend to be on the left side of PC1.


# PROJECTION OF ILLUSTRATIVE qualitative variables on individuals' map
varcat=factor(dd[,18])
plot(Psi[,1],Psi[,2],col=rainbow(9)[varcat])
axis(side=1, pos= 0, labels = F, col="darkgray")
axis(side=3, pos= 0, labels = F, col="darkgray")
axis(side=2, pos= 0, labels = F, col="darkgray")
axis(side=4, pos= 0, labels = F, col="darkgray")
legend("bottomleft",levels(varcat),pch=1,col=rainbow(9), cex=0.6)


# Overproject THE CDG OF  LEVELS OF varcat
fdic1 = tapply(Psi[,1],varcat,mean)
fdic2 = tapply(Psi[,2],varcat,mean) 

text(fdic1,fdic2,labels=levels(factor(varcat)),col="cyan", cex=0.75)

From the tempo categories plot we see that the left side of PCA is the faster songs, and the right side are the slower songs.

LS0tCnRpdGxlOiAiU3BvdGlmeSBkYXRhIC0gUHJpbmNpcGFsIENvbXBvbmVudCBBbmFseXNpcyIKb3V0cHV0OgogIHdvcmRfZG9jdW1lbnQ6IGRlZmF1bHQKICBodG1sX25vdGVib29rOiBkZWZhdWx0Ci0tLQoKIyMgSW50cm9kdWN0aW9uCgpJbiB0aGlzIHJlcG9ydCwgd2Ugd2lsbCBiZSBkb2luZyBhIFByaW5jaXBhbCBDb21wb25lbnQgYW5hbHlzaXMgYmFzZWQgb24gU3BvdGlmeSBkYXRhIG9uIHBvcHVsYXIgc29uZ3MuCgpBIFByaW5jaXBhbCBDb21wb25lbnQgQW5hbHlzaXMgaXMgYSB0ZWNobmlxdWUgdG8gYW5hbHl6ZSBsYXJnZSBkYXRhc2V0cyBjb250YWluaW5nIG11bHRpcGxlIGRpbWVuc2lvbnMvZmVhdHVyZXMuIFRoZSBwdXJwb3NlIGlzIHRvIGVuYWJsZSB2aXN1YWxpemF0aW9uIG9mIG11bHRpZGltZW5zaW9uYWwgZGF0YS4KClBDQSBpZGVudGlmaWVzIHRoZSBtYWluIGF4ZXMgb2YgdmFyaWFuY2Ugd2l0aGluIGEgZGF0YSBzZXQgYW5kIGFsbG93cyBmb3IgZWFzeSBkYXRhIGV4cGxvcmF0aW9uIHRvIHVuZGVyc3RhbmQgdGhlIGtleSB2YXJpYWJsZXMgaW4gdGhlIGRhdGEgYW5kIHNwb3Qgb3V0bGllcnMuCgpUaGUgZ29hbCBpcyB0byBkZXRlcm1pbmUgd2hpY2ggdmFyaWFibGVzIGFyZSByZWxhdGVkIG9yIG5vdCByZWxhdGVkIHRvIGVhY2ggb3RoZXIuCgpgYGB7ciwgcmVzdWx0cz1GQUxTRX0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoamFuaXRvcikKYGBgCgojIyBJbXBvcnRpbmcgdGhlIGRhdGEKCldlIGFyZSB1c2luZyBhIGRhdGFzZXQgb2YgcG9wdWxhciBzb25ncyBvbiBTcG90aWZ5LiBJbiB0aGUgcHJldmlvdXMgcmVwb3J0IG9uIHByZS1wcm9jZXNzaW5nLCBkZXNjcmlwdGl2ZSBhbmQgYml2YXJpYXRlIHN0YXRpc3RpY3MsIHdlIGhhdmUgZGVzY3JpYmVkIHRoaXMgZGF0YXNldCBhbmQgbWFkZSBzZXZlcmFsIHRyYW5zZm9ybWF0aW9ucy4KCltMaW5rIHRvIG9yaWdpbmFsIGRhdGFzZXRdKGh0dHBzOi8vd3d3LmthZ2dsZS5jb20vZGF0YXNldHMvbWFoYXJzaGlwYW5keWEvLXNwb3RpZnktdHJhY2tzLWRhdGFzZXQpCgpgYGB7cn0Kc2V0d2QoIn4vRG9jdW1lbnRzL2NsYXNzL3N0YXRzLWZpbmFsLXByb2plY3QvIikKZGQgPC0gcmVhZC5jc3YoImNsZWFuZWRkYXRhLmNzdiIpCmBgYAoKIyMgUGVyZm9ybWluZyB0aGUgUHJpbmNpcGFsIENvbXBvbmVudCBBbmFseXNpcwoKV2UgdXNlIHRoZSBgcHJjb21wKClgIGZ1bmN0aW9uLgoKVGhpcyByZXR1cm5zIDMgdGhpbmdzOgoKMS4geCA9PiBjb250YWlucyB0aGUgcHJpbmNpcGFsIGNvbXBvbmVudHMgKFBDcykgZm9yIGRyYXdpbmcgYSBncmFwaC4gV2Ugd2lsbCBiZSB1c2luZyB0aGUgZmlyc3QgdHdvIGNvbHVtbnMgaW4geCB0byBkcmF3IGEgMkQgcGxvdCB0aGF0IHVzZXMgdGhlIGZpcnN0IDIgUENzLiBUaGUgbnVtYmVyIG9mIFBDcyBpcyBkZXRlcm1pbmVkIGJ5IHRoZSBudW1iZXIgb2YgdmFyaWFibGVzIHVzZWQuCgoyLiBzZGV2CgozLiByb3RhdGlvbgoKQmVsb3cgaXMgdGhlIGNvZGUgdG8gcnVuIHRoZSBwcmNvbXAgZnVuY3Rpb24sIGFuZCBhIGJhc2ljIHBsb3Qgb2YgcHJpbmNpcGFsIGNvbXBvbmVudCAxIGFuZCAyLgoKYGBge3J9CiMgZGV0ZXJtaW5lIHdoaWNoIG9uZXMgYXJlIG51bWVyaWNhbCB2YXJpYWJsZXMKbnVtZXJpY2FsIDwtIHdoaWNoKHNhcHBseShkZCxpcy5udW1lcmljKSkKIyBwcmludCBiZWxvdyB0byBzZWUgaWYgdGhlIG51bWVyaWNhbCB2YXJpYWJsZXMgYXJlIGNvcnJlY3RseSBkZXRlY3RlZAojIG51bWVyaWNhbAoKIyBzYXZpbmcgdGhlIG51bWVyaWNhbCBvYnNlcnZhdGlvbnMgdG8gImRjb24iCmRjb24gPC0gZGRbLG51bWVyaWNhbF0KIyBwcmludCBiZWxvdyB0byBzZWUgaWYgdmFyaWFibGVzIGRldGVjdGVkIGFyZSBpbmRlZWQgbnVtZXJpY2FsCiMgc2FwcGx5KGRjb24sY2xhc3MpCgojIE5vdyB3ZSBkbyBhIFBSSU5DSVBBTCBDT01QT05FTlQgQU5BTFlTSVMgb24gdGhlIG51bWVyaWNhbCB2YXJpYWJsZXMKcGNhIDwtIHByY29tcChkY29uLCBzY2FsZT1UUlVFLCBjZW50ZXIgPSBUUlVFKSAjIGNlbnRlcmluZyBhbmQgc2NhbGluZyB0cnVlCnBjMSA8LSBwY2EKCnBsb3QocGNhJHhbLDFdLCBwY2EkeFssMl0pCgpgYGAKCiMjIyBTY3JlZSBwbG90CgpXaXRoIHRoZSBwcmluY2lwYWwgY29tcG9uZW50IGFuYWx5c2lzLCB3ZSBjYW4gYWxzbyBjb21wdXRlIHRoZSBTY3JlZSBwbG90LCB3aGljaCBkaXNwbGF5cyB0aGUgdmFyaWFuY2UgYWNjb3VudGVkIGZvciBieSB0aGUgY29tcG9uZW50cy4KCmBgYHtyfQpwY2EudmFyIDwtIHBjYSRzZGV2XjIKcGNhLnZhci5wZXIgPC0gcm91bmQocGNhLnZhci9zdW0ocGNhLnZhcikqMTAwLCAxKQpwY2EudmFyLnBlcgpiYXJwbG90KHBjYS52YXIucGVyLCBtYWluPSJTY3JlZSBQbG90IiwgeGxhYj0iUHJpbmNpcGFsIENvbXBvbmVudCIsIHlsYWI9IlBlcmNlbnQgVmFyaWF0aW9uIikKCiNDdW1tdWxhdGVkIEluZXJ0aWEgaW4gc3Vic3BhY2VzLCBmcm9tIGZpcnN0IHByaW5jaXBhbCBjb21wb25lbnQgdG8gdGhlIDExdGggZGltZW5zaW9uIHN1YnNwYWNlCmJhcnBsb3QoMTAwKmN1bXN1bShwYzEkc2RldlsxOmRpbShkY29uKVsyXV1eMikvZGltKGRjb24pWzJdKQpwZXJjSW5lckFjY3VtPC0xMDAqY3Vtc3VtKHBjMSRzZGV2WzE6ZGltKGRjb24pWzJdXV4yKS9kaW0oZGNvbilbMl0KcGVyY0luZXJBY2N1bQpgYGAKCkZyb20gdGhpcyB3ZSBzZWUgdGhhdCBQcmluY2lwYWwgY29tcG9uZW50IDEgYWNjb3VudHMgZm9yIG9ubHkgMjUuMiUgb2YgdGhlIHZhcmlhdGlvbi4gQW5kIGluIG9yZGVyIHRvIGFjY291bnQgZm9yIDgwJSBvZiB0aGUgdmFyaWF0aW9uLCB3ZSBuZWVkIHRvIGluY2x1ZGUgUEMgMS03LgoKTmV4dCB3ZSB3aWxsIHN0b3JlIHRoZSBlaWdlbnZhbHVlcywgZWlnZW52ZWN0b3JzLCBwcm9qZWN0aW9ucyBhbmQgaW5jbHVkZSBQQyAxLTcuCgpgYGB7ciwgcmVzdWx0cz1GQUxTRX0KIyBTRUxFQ1RJT04gT0YgVEhFIFNJTkdJRklDQU5UIERJTUVOU0lPTlMgKGtlZXAgODAlIG9mIHRvdGFsIGluZXJ0aWEpCm5kID0gNwpwYzEkcm90YXRpb24KCiMgU1RPUkFHRSBPRiBUSEUgRUlHRU5WQUxVRVMsIEVJR0VOVkVDVE9SUyBBTkQgUFJPSkVDVElPTlMgSU4gVEhFIG5kIERJTUVOU0lPTlMKUHNpID0gcGMxJHhbLDE6bmRdClBzaQoKCiMgU1RPUkFHRSBPRiBMQUJFTFMgRk9SIElORElWSURVQUxTIEFORCBWQVJJQUJMRVMKaWRlbiA9IHJvdy5uYW1lcyhkY29uKQpldGlxID0gbmFtZXMoZGNvbikgIyBnZXR0aW5nIG5hbWVzIG9mIG51bWVyaWNhbCB2YXJpYWJsZXMKemUgPSByZXAoMCxsZW5ndGgoZXRpcSkpICMgV0UgV0lMTCBORUVEIFRISVMgVkVDVE9SIEFGVEVSV0FSRFMgRk9SIFRIRSBHUkFQSElDUwpgYGAKCiMjIFBsb3R0aW5nIHRoZSBpbmRpdmlkdWFscyBvbiBQQzEgYW5kIFBDMiBheGVzCgpgYGB7cn0KIyBQTE9UIE9GIElORElWSURVQUxTCgojc2VsZWN0IHlvdXIgYXhpcwojZWplMTwtMgplamUxPC0xCiNlamUyPC0zCmVqZTI8LTIKCnBsb3QoUHNpWyxlamUxXSxQc2lbLGVqZTJdKQp0ZXh0KFBzaVssZWplMV0sUHNpWyxlamUyXSxsYWJlbHM9aWRlbiwgY2V4PTAuNSkKYXhpcyhzaWRlPTEsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTMsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTQsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYGBgCgojIyBQbG90dGluZyBwcm9qZWN0aW9uIG9mIHZhcmlhYmxlcywgUEMxIGFuZCBQQzIKCldlIHdpbGwgY3JlYXRlIGEgbG9hZGluZ3MgcGxvdCB0byBzZWUgd2hpY2ggdmFyaWFibGVzIG1vc3QgaW5mbHVlbmNlIFBDMSBhbmQgUEMyLgoKYGBge3J9CiNQcm9qZWN0aW9uIG9mIHZhcmlhYmxlcwoKUGhpID0gY29yKGRjb24sUHNpKQpQaGkKClg8LVBoaVssZWplMV0KWTwtUGhpWyxlamUyXQoKI3pvb21zCnBsb3QoUHNpWyxlamUxXSxQc2lbLGVqZTJdLHR5cGU9Im4iLHhsaW09YyhtaW4oWCwwKSxtYXgoWCwwKSksIHlsaW09YygtMSwxKSkKYXhpcyhzaWRlPTEsIHBvcz0gMCwgbGFiZWxzID0gRikKYXhpcyhzaWRlPTMsIHBvcz0gMCwgbGFiZWxzID0gRikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRikKYXhpcyhzaWRlPTQsIHBvcz0gMCwgbGFiZWxzID0gRikKYXJyb3dzKHplLCB6ZSwgWCwgWSwgbGVuZ3RoID0gMC4wNyxjb2w9ImJsdWUiKQp0ZXh0KFgsWSxsYWJlbHM9ZXRpcSxjb2w9ImRhcmtibHVlIiwgY2V4PTAuNykKYGBgCgojIyMgT2JzZXJ2YXRpb25zOgoKQmFzZWQgb24gdGhlICBMb2FkaW5ncyBwbG90LCB3ZSBzZWUgdGhhdCB0aGUgdmFyaWFibGVzIHRoYXQgbW9zdCBpbmZsdWVuY2UgUEMxIGFyZSBpbnN0cnVtZW50YWxuZXNzLCBlbmVyZ3ksIGxvdWRuZXNzLCBhbmQgYWNvdXN0aWNuZXNzLgoKVGhlIHZhcmlhYmxlcyB0aGF0IG1vc3QgaW5mbHVlbmNlIFBDMiBhcmUgZHVyYXRpb24uCgpGcm9tIHRoaXMgcGxvdCB3ZSBjYW4gYWxzbyBzZWUgdGhhdCB0aGVzZSB2YXJpYWJsZXMgbWF5IGJlIHBvc2l0aXZlbHkgY29ycmVsYXRlZDoKLSBMb3VkbmVzcyBhbmQgZW5lcmd5Ci0gVmFsZW5jZSBhbmQgZGFuY2VhYmlsaXR5Ci0gSW5zdHJ1bWVudGFsbmVzcyBhbmQgYWNvdXN0aWNuZXNzCgpUaGVzZSB2YXJpYWJsZXMgbWF5IGJlIG5lZ2F0aXZlbHkgY29ycmVsYXRlZDoKLSBMb3VkbmVzcyBhbmQgaW5zdHJ1bWVudGFsbmVzcwotIExvdWRuZXNzIGFuZCBhY291c3RpY25lc3MKLSBFbmVyZ3kgYW5kIGFjb3VzdGljbmVzcwotIFZhbGVuY2UgYW5kIGluc3RydW1lbnRhbG5lc3MKLSBUZW1wbyBhbmQgYWNvdXN0aWNuZXNzCgpXZSBjYW4gYWxzbyB0cnkgcGxvdHRpbmcgdGhlIFBDMSBhZ2FpbnN0IFBDMyB0byBzZWUgdGhlIHZhcmlhYmxlcyB0aGF0IGFyZSBub3Qgc28gY2xlYXJseSB2aXNpYmxlIGhlcmUuCgojIyBQbG90dGluZyBwcm9qZWN0aW9uIG9mIHZhcmlhYmxlcywgUEMxIGFuZCBQQzMKClNpbmNlIFBDMSBhbmQgUEMyIG9ubHkgYWNjb3VudHMgZm9yIDM4JSBvZiB0aGUgdmFyaWF0aW9uLCB3ZSBzaG91bGQgYWxzbyBwbG90IHByb2plY3Rpb24gb2YgdmFyaWFibGVzIGluIFBDMSBhbmQgUEMzLgoKYGBge3J9CiNQcm9qZWN0aW9uIG9mIHZhcmlhYmxlcwoKUGhpID0gY29yKGRjb24sUHNpKQpQaGkKCmVqZTMgPC0gMwoKWDwtUGhpWyxlamUxXQpZPC1QaGlbLGVqZTNdCgojem9vbXMKcGxvdChQc2lbLGVqZTFdLFBzaVssZWplM10sdHlwZT0ibiIseGxpbT1jKG1pbihYLDApLG1heChYLDApKSwgeWxpbT1jKC0xLDEpKQpheGlzKHNpZGU9MSwgcG9zPSAwLCBsYWJlbHMgPSBGKQpheGlzKHNpZGU9MywgcG9zPSAwLCBsYWJlbHMgPSBGKQpheGlzKHNpZGU9MiwgcG9zPSAwLCBsYWJlbHMgPSBGKQpheGlzKHNpZGU9NCwgcG9zPSAwLCBsYWJlbHMgPSBGKQphcnJvd3MoemUsIHplLCBYLCBZLCBsZW5ndGggPSAwLjA3LGNvbD0iYmx1ZSIpCnRleHQoWCxZLGxhYmVscz1ldGlxLGNvbD0iZGFya2JsdWUiLCBjZXg9MC43KQpgYGAKCkJhc2VkIG9uIHRoZSBhYm92ZSBMb2FkaW5ncyBwbG90LCB3ZSBzZWUgdGhhdCB0aGUgdmFyaWFibGVzIHRoYXQgbW9zdCBpbmZsdWVuY2UgUEMzIGFyZSBwb3B1bGFyaXR5LCBsaXZlbmVzcyBhbmQgZHVyYXRpb24uCgpJdCBhbHNvIHNlZW1zIGxpa2UgUG9wdWxhcml0eSBhbmQgbGl2ZW5lc3MgYXJlIGNsb3NlbHkgcmVsYXRlZCwgd2hpbGUgaXQgbWF5IGJlIG5lZ2F0aXZlbHkgY29ycmVsYXRlZCB3aXRoIGR1cmF0aW9uLgoKV2UgY2FuIGFsc28gc2VlIHRoYXQgc3BlZWNoaW5lc3MgaXMgY2xvc2VyIHRvIGRhbmNlYWJpbGl0eS4KCiMjIEZpbmRpbmcgQ2VudHJvaWRzCgpXZSBjYW4gYWxzbyBmaW5kIHRoZSBjZW50cm9pZHMgb2YgbW9kYWxpdGllcyBpbiBjYXRlZ29yaWNhbCB2YXJpYWJsZXMsIHVzaW5nIHRoZSBjb2RlIGJlbG93LgoKYGBge3J9CgpYPC1QaGlbLGVqZTFdClk8LVBoaVssZWplMl0KCnBsb3QoUHNpWyxlamUxXSxQc2lbLGVqZTJdLHR5cGU9Im4iLHhsaW09YygtMSwxKSwgeWxpbT1jKC0zLDEpKQojcGxvdChYLFksdHlwZT0ibm9uZSIseGxpbT1jKG1pbihYLDApLG1heChYLDApKSkKYXhpcyhzaWRlPTEsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTMsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTQsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKCmFycm93cyh6ZSwgemUsIFgsIFksIGxlbmd0aCA9IDAuMDcsY29sPSJsaWdodGdyYXkiKQp0ZXh0KFgsWSxsYWJlbHM9ZXRpcSxjb2w9ImdyYXkiLCBjZXg9MC43KQoKI2FsbCBxdWFsaXRhdGl2ZSB0b2dldGhlcgpwbG90KFBzaVssZWplMV0sUHNpWyxlamUyXSx0eXBlPSJuIix4bGltPWMoLTIsNCksIHlsaW09YygtMiwyKSkKYXhpcyhzaWRlPTEsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTMsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTQsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXJyb3dzKHplLCB6ZSwgWCwgWSwgbGVuZ3RoID0gMC4wNyxjb2w9ImxpZ2h0Z3JheSIpCnRleHQoWCxZLGxhYmVscz1ldGlxLGNvbD0iZ3JheSIsIGNleD0wLjcpCgojbm9taW5hbCBxdWFsaXRhdGl2ZSB2YXJpYWJsZXMKCmRjYXQ8LWMoMywgNiwgOCwgMTYsIDE3KQpjb2xvcnM8LXJhaW5ib3cobGVuZ3RoKGRjYXQpKQoKYzwtMQpmb3IoayBpbiBkY2F0KXsKICBzZWd1ZW50Q29sb3I8LWNvbG9yc1tjXQpmZGljMSA9IHRhcHBseShQc2lbLGVqZTFdLGRkWyxrXSxtZWFuKQpmZGljMiA9IHRhcHBseShQc2lbLGVqZTJdLGRkWyxrXSxtZWFuKSAKCnRleHQoZmRpYzEsZmRpYzIsbGFiZWxzPWxldmVscyhmYWN0b3IoZGRbLGtdKSksY29sPXNlZ3VlbnRDb2xvciwgY2V4PTAuNikKYzwtYysxCn0KbGVnZW5kKCJib3R0b21sZWZ0IixuYW1lcyhkZClbZGNhdF0scGNoPTEsY29sPWNvbG9ycywgY2V4PTAuNikKCiNhZGQgb3JkaW5hbCBxdWFsaXRhdGl2ZSB2YXJpYWJsZXMuIEVuc3VyZSBvcmRlcmluZyBpcyB0aGUgY29ycmVjdAoKZG9yZGk8LWMoMTgpCgoKI3Jlb3JkZXIgbW9kYWxpdGllczogd2hlbiByZXF1aXJlZApkZFssZG9yZGlbMV1dIDwtIGZhY3RvcihkZFssZG9yZGlbMV1dLCBvcmRlcmVkPVRSVUUsICBsZXZlbHM9IGMoJ0xhcmdoaXNzaW1vJywnR3JhdmUnLCdMZW50by9MYXJnbycsJ0xhcmdoZXR0bycsJ0FkYWdpbycsJ0FuZGFudGUnLCdNb2RlcmF0bycsJ0FsbGVncm8nLCdWaXZhY2UnLCdQcmVzdG8nLCdQcmVzdGlzc2ltbycpKQpsZXZlbHMoZGRbLGRvcmRpWzFdXSkKCmM8LTEKY29sPC1sZW5ndGgoZGNhdCkrMQpmb3IoayBpbiBkb3JkaSl7CiAgc2VndWVudENvbG9yPC1jb2xvcnNbY29sXQogIGZkaWMxID0gdGFwcGx5KFBzaVssZWplMV0sZGRbLGtdLG1lYW4pCiAgZmRpYzIgPSB0YXBwbHkoUHNpWyxlamUyXSxkZFssa10sbWVhbikgCiAgCiAgI3BvaW50cyhmZGljMSxmZGljMixwY2g9MTYsY29sPXNlZ3VlbnRDb2xvciwgbGFiZWxzPWxldmVscyhkZFssa10pKQogICNjb25uZWN0IG1vZGFsaXRpZXMgb2YgcXVhbGl0YXRpdmUgdmFyaWFibGVzCiAgbGluZXMoZmRpYzEsZmRpYzIsY29sPSIjMDAwMDAwIikKICB0ZXh0KGZkaWMxLGZkaWMyLGxhYmVscz1sZXZlbHMoZGRbLGtdKSxjb2w9c2VndWVudENvbG9yLCBjZXg9MC42KQogIGM8LWMrMQogIGNvbDwtY29sKzEKfQpsZWdlbmQoInRvcGxlZnQiLG5hbWVzKGRkKVtkb3JkaV0scGNoPTE5LGNvbD1jb2xvcnNbY29sOmNvbCtsZW5ndGgoZG9yZGkpLTFdLCBjZXg9MC42KQpgYGAKClRoYXQgbG9va3MgYSBiaXQgY3Jvd2RlZCwgc28gbGV0J3MgdHJ5IGxvb2tpbmcgYXQgdGhlIG1vZGFsaXRpZXMgb25lIGJ5IG9uZS4KCiMjIyBFeHBsaWNpdAoKYGBge3J9CiNhbGwgcXVhbGl0YXRpdmUgdG9nZXRoZXIKcGxvdChQc2lbLGVqZTFdLFBzaVssZWplMl0sdHlwZT0ibiIseGxpbT1jKC0xLDEpLCB5bGltPWMoLTEsMSkpCmF4aXMoc2lkZT0xLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT0zLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT0yLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT00LCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmFycm93cyh6ZSwgemUsIFgsIFksIGxlbmd0aCA9IDAuMDcsY29sPSJsaWdodGdyYXkiKQp0ZXh0KFgsWSxsYWJlbHM9ZXRpcSxjb2w9ImdyYXkiLCBjZXg9MC43KQoKI25vbWluYWwgcXVhbGl0YXRpdmUgdmFyaWFibGVzCgpkY2F0PC1jKDMpCmNvbG9yczwtcmFpbmJvdyhsZW5ndGgoZGNhdCkpCgpjPC0xCmZvcihrIGluIGRjYXQpewogIHNlZ3VlbnRDb2xvcjwtY29sb3JzW2NdCmZkaWMxID0gdGFwcGx5KFBzaVssZWplMV0sZGRbLGtdLG1lYW4pCmZkaWMyID0gdGFwcGx5KFBzaVssZWplMl0sZGRbLGtdLG1lYW4pIAoKdGV4dChmZGljMSxmZGljMixsYWJlbHM9bGV2ZWxzKGZhY3RvcihkZFssa10pKSxjb2w9c2VndWVudENvbG9yLCBjZXg9MC42KQpjPC1jKzEKfQpsZWdlbmQoImJvdHRvbWxlZnQiLG5hbWVzKGRkKVtkY2F0XSxwY2g9MSxjb2w9Y29sb3JzLCBjZXg9MC42KQoKCmBgYAoKIyMjIEtleQoKYGBge3J9CiNhbGwgcXVhbGl0YXRpdmUgdG9nZXRoZXIKcGxvdChQc2lbLGVqZTFdLFBzaVssZWplMl0sdHlwZT0ibiIseGxpbT1jKC0xLDEpLCB5bGltPWMoLTEsMSkpCmF4aXMoc2lkZT0xLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT0zLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT0yLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT00LCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmFycm93cyh6ZSwgemUsIFgsIFksIGxlbmd0aCA9IDAuMDcsY29sPSJsaWdodGdyYXkiKQp0ZXh0KFgsWSxsYWJlbHM9ZXRpcSxjb2w9ImdyYXkiLCBjZXg9MC43KQoKI25vbWluYWwgcXVhbGl0YXRpdmUgdmFyaWFibGVzCgpkY2F0PC1jKDYpCmNvbG9yczwtcmFpbmJvdyhsZW5ndGgoZGNhdCkpCgpjPC0xCmZvcihrIGluIGRjYXQpewogIHNlZ3VlbnRDb2xvcjwtY29sb3JzW2NdCmZkaWMxID0gdGFwcGx5KFBzaVssZWplMV0sZGRbLGtdLG1lYW4pCmZkaWMyID0gdGFwcGx5KFBzaVssZWplMl0sZGRbLGtdLG1lYW4pIAoKdGV4dChmZGljMSxmZGljMixsYWJlbHM9bGV2ZWxzKGZhY3RvcihkZFssa10pKSxjb2w9c2VndWVudENvbG9yLCBjZXg9MC42KQpjPC1jKzEKfQpsZWdlbmQoImJvdHRvbWxlZnQiLG5hbWVzKGRkKVtkY2F0XSxwY2g9MSxjb2w9Y29sb3JzLCBjZXg9MC42KQoKCmBgYAoKCiMjIE1vZGUKCmBgYHtyfQojYWxsIHF1YWxpdGF0aXZlIHRvZ2V0aGVyCnBsb3QoUHNpWyxlamUxXSxQc2lbLGVqZTJdLHR5cGU9Im4iLHhsaW09YygtMSwxKSwgeWxpbT1jKC0xLDEpKQpheGlzKHNpZGU9MSwgcG9zPSAwLCBsYWJlbHMgPSBGLCBjb2w9ImN5YW4iKQpheGlzKHNpZGU9MywgcG9zPSAwLCBsYWJlbHMgPSBGLCBjb2w9ImN5YW4iKQpheGlzKHNpZGU9MiwgcG9zPSAwLCBsYWJlbHMgPSBGLCBjb2w9ImN5YW4iKQpheGlzKHNpZGU9NCwgcG9zPSAwLCBsYWJlbHMgPSBGLCBjb2w9ImN5YW4iKQphcnJvd3MoemUsIHplLCBYLCBZLCBsZW5ndGggPSAwLjA3LGNvbD0ibGlnaHRncmF5IikKdGV4dChYLFksbGFiZWxzPWV0aXEsY29sPSJncmF5IiwgY2V4PTAuNykKCiNub21pbmFsIHF1YWxpdGF0aXZlIHZhcmlhYmxlcwoKZGNhdDwtYyg4KQpjb2xvcnM8LXJhaW5ib3cobGVuZ3RoKGRjYXQpKQoKYzwtMQpmb3IoayBpbiBkY2F0KXsKICBzZWd1ZW50Q29sb3I8LWNvbG9yc1tjXQpmZGljMSA9IHRhcHBseShQc2lbLGVqZTFdLGRkWyxrXSxtZWFuKQpmZGljMiA9IHRhcHBseShQc2lbLGVqZTJdLGRkWyxrXSxtZWFuKSAKCnRleHQoZmRpYzEsZmRpYzIsbGFiZWxzPWxldmVscyhmYWN0b3IoZGRbLGtdKSksY29sPXNlZ3VlbnRDb2xvciwgY2V4PTAuNikKYzwtYysxCn0KbGVnZW5kKCJib3R0b21sZWZ0IixuYW1lcyhkZClbZGNhdF0scGNoPTEsY29sPWNvbG9ycywgY2V4PTAuNikKCgpgYGAKIyMgTXVsdGlwbGUgYXJ0aXN0cwoKYGBge3J9CiNhbGwgcXVhbGl0YXRpdmUgdG9nZXRoZXIKcGxvdChQc2lbLGVqZTFdLFBzaVssZWplMl0sdHlwZT0ibiIseGxpbT1jKC0xLDMpLCB5bGltPWMoLTIsMikpCmF4aXMoc2lkZT0xLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT0zLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT0yLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmF4aXMoc2lkZT00LCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iY3lhbiIpCmFycm93cyh6ZSwgemUsIFgsIFksIGxlbmd0aCA9IDAuMDcsY29sPSJsaWdodGdyYXkiKQp0ZXh0KFgsWSxsYWJlbHM9ZXRpcSxjb2w9ImdyYXkiLCBjZXg9MC43KQoKI25vbWluYWwgcXVhbGl0YXRpdmUgdmFyaWFibGVzCgpkY2F0PC1jKDE3KQpjb2xvcnM8LXJhaW5ib3cobGVuZ3RoKGRjYXQpKQoKYzwtMQpmb3IoayBpbiBkY2F0KXsKICBzZWd1ZW50Q29sb3I8LWNvbG9yc1tjXQpmZGljMSA9IHRhcHBseShQc2lbLGVqZTFdLGRkWyxrXSxtZWFuKQpmZGljMiA9IHRhcHBseShQc2lbLGVqZTJdLGRkWyxrXSxtZWFuKSAKCnRleHQoZmRpYzEsZmRpYzIsbGFiZWxzPWxldmVscyhmYWN0b3IoZGRbLGtdKSksY29sPXNlZ3VlbnRDb2xvciwgY2V4PTAuNikKYzwtYysxCn0KbGVnZW5kKCJib3R0b21sZWZ0IixuYW1lcyhkZClbZGNhdF0scGNoPTEsY29sPWNvbG9ycywgY2V4PTAuNikKCgpgYGAKCgpBbGwgZXhjZXB0IGdlbnJlCmBgYHtyfQoKI2FsbCBxdWFsaXRhdGl2ZSB0b2dldGhlcgpwbG90KFBzaVssZWplMV0sUHNpWyxlamUyXSx0eXBlPSJuIix4bGltPWMoLTEsMyksIHlsaW09YygtMiwyKSkKYXhpcyhzaWRlPTEsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTMsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTQsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXJyb3dzKHplLCB6ZSwgWCwgWSwgbGVuZ3RoID0gMC4wNyxjb2w9ImxpZ2h0Z3JheSIpCnRleHQoWCxZLGxhYmVscz1ldGlxLGNvbD0iZ3JheSIsIGNleD0wLjcpCgojbm9taW5hbCBxdWFsaXRhdGl2ZSB2YXJpYWJsZXMKCmRjYXQ8LWMoMyw2LDgsMTcpCmNvbG9yczwtcmFpbmJvdyhsZW5ndGgoZGNhdCkpCgpjPC0xCmZvcihrIGluIGRjYXQpewogIHNlZ3VlbnRDb2xvcjwtY29sb3JzW2NdCmZkaWMxID0gdGFwcGx5KFBzaVssZWplMV0sZGRbLGtdLG1lYW4pCmZkaWMyID0gdGFwcGx5KFBzaVssZWplMl0sZGRbLGtdLG1lYW4pIAoKdGV4dChmZGljMSxmZGljMixsYWJlbHM9bGV2ZWxzKGZhY3RvcihkZFssa10pKSxjb2w9c2VndWVudENvbG9yLCBjZXg9MC42KQpjPC1jKzEKfQpsZWdlbmQoImJvdHRvbWxlZnQiLG5hbWVzKGRkKVtkY2F0XSxwY2g9MSxjb2w9Y29sb3JzLCBjZXg9MC42KQoKCgojYWRkIG9yZGluYWwgcXVhbGl0YXRpdmUgdmFyaWFibGVzLiBFbnN1cmUgb3JkZXJpbmcgaXMgdGhlIGNvcnJlY3QKCmRvcmRpPC1jKDE4KQoKCiNyZW9yZGVyIG1vZGFsaXRpZXM6IHdoZW4gcmVxdWlyZWQKZGRbLGRvcmRpWzFdXSA8LSBmYWN0b3IoZGRbLGRvcmRpWzFdXSwgb3JkZXJlZD1UUlVFLCAgbGV2ZWxzPSBjKCdMYXJnaGlzc2ltbycsJ0dyYXZlJywnTGVudG8vTGFyZ28nLCdMYXJnaGV0dG8nLCdBZGFnaW8nLCdBbmRhbnRlJywnTW9kZXJhdG8nLCdBbGxlZ3JvJywnVml2YWNlJywnUHJlc3RvJywnUHJlc3Rpc3NpbW8nKSkKbGV2ZWxzKGRkWyxkb3JkaVsxXV0pCgpjPC0xCmNvbDwtbGVuZ3RoKGRjYXQpKzEKZm9yKGsgaW4gZG9yZGkpewogIHNlZ3VlbnRDb2xvcjwtY29sb3JzW2NvbF0KICBmZGljMSA9IHRhcHBseShQc2lbLGVqZTFdLGRkWyxrXSxtZWFuKQogIGZkaWMyID0gdGFwcGx5KFBzaVssZWplMl0sZGRbLGtdLG1lYW4pIAogIAogICNwb2ludHMoZmRpYzEsZmRpYzIscGNoPTE2LGNvbD1zZWd1ZW50Q29sb3IsIGxhYmVscz1sZXZlbHMoZGRbLGtdKSkKICAjY29ubmVjdCBtb2RhbGl0aWVzIG9mIHF1YWxpdGF0aXZlIHZhcmlhYmxlcwogIGxpbmVzKGZkaWMxLGZkaWMyLGNvbD0iIzAwMDAwMCIpCiAgdGV4dChmZGljMSxmZGljMixsYWJlbHM9bGV2ZWxzKGRkWyxrXSksY29sPXNlZ3VlbnRDb2xvciwgY2V4PTAuNikKICBjPC1jKzEKICBjb2w8LWNvbCsxCn0KbGVnZW5kKCJ0b3BsZWZ0IixuYW1lcyhkZClbZG9yZGldLHBjaD0xOSxjb2w9Y29sb3JzW2NvbDpjb2wrbGVuZ3RoKGRvcmRpKS0xXSwgY2V4PTAuNikKCgpgYGAKCmBgYHtyfQoKI2FsbCBxdWFsaXRhdGl2ZSB0b2dldGhlcgpwbG90KFBzaVssZWplMV0sUHNpWyxlamUyXSx0eXBlPSJuIix4bGltPWMoLTEsMyksIHlsaW09YygtMSwxKSkKYXhpcyhzaWRlPTEsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTMsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXhpcyhzaWRlPTQsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJjeWFuIikKYXJyb3dzKHplLCB6ZSwgWCwgWSwgbGVuZ3RoID0gMC4wNyxjb2w9ImxpZ2h0Z3JheSIpCnRleHQoWCxZLGxhYmVscz1ldGlxLGNvbD0iZ3JheSIsIGNleD0wLjcpCgoKI2FkZCBvcmRpbmFsIHF1YWxpdGF0aXZlIHZhcmlhYmxlcy4gRW5zdXJlIG9yZGVyaW5nIGlzIHRoZSBjb3JyZWN0Cgpkb3JkaTwtYygxOCkKCgojcmVvcmRlciBtb2RhbGl0aWVzOiB3aGVuIHJlcXVpcmVkCmRkWyxkb3JkaVsxXV0gPC0gZmFjdG9yKGRkWyxkb3JkaVsxXV0sIG9yZGVyZWQ9VFJVRSwgIGxldmVscz0gYygnTGFyZ2hpc3NpbW8nLCdHcmF2ZScsJ0xlbnRvL0xhcmdvJywnTGFyZ2hldHRvJywnQWRhZ2lvJywnQW5kYW50ZScsJ01vZGVyYXRvJywnQWxsZWdybycsJ1ZpdmFjZScsJ1ByZXN0bycsJ1ByZXN0aXNzaW1vJykpCmxldmVscyhkZFssZG9yZGlbMV1dKQoKYzwtMQpjb2w8LWxlbmd0aChkY2F0KSsxCmZvcihrIGluIGRvcmRpKXsKICBzZWd1ZW50Q29sb3I8LWNvbG9yc1tjb2xdCiAgZmRpYzEgPSB0YXBwbHkoUHNpWyxlamUxXSxkZFssa10sbWVhbikKICBmZGljMiA9IHRhcHBseShQc2lbLGVqZTJdLGRkWyxrXSxtZWFuKSAKICAKICAjcG9pbnRzKGZkaWMxLGZkaWMyLHBjaD0xNixjb2w9c2VndWVudENvbG9yLCBsYWJlbHM9bGV2ZWxzKGRkWyxrXSkpCiAgI2Nvbm5lY3QgbW9kYWxpdGllcyBvZiBxdWFsaXRhdGl2ZSB2YXJpYWJsZXMKICBsaW5lcyhmZGljMSxmZGljMixjb2w9IiMwMDAwMDAiKQogIHRleHQoZmRpYzEsZmRpYzIsbGFiZWxzPWxldmVscyhkZFssa10pLGNvbD1zZWd1ZW50Q29sb3IsIGNleD0wLjYpCiAgYzwtYysxCiAgY29sPC1jb2wrMQp9CmxlZ2VuZCgidG9wbGVmdCIsbmFtZXMoZGQpW2RvcmRpXSxwY2g9MTksY29sPWNvbG9yc1tjb2w6Y29sK2xlbmd0aChkb3JkaSktMV0sIGNleD0wLjYpCgoKYGBgCgoKT2JzZXJ2YXRpb25zIGZyb20gdGhlIHBsb3Qgb2YgY2VudHJvaWRzIGFib3ZlOgoKMS4gU29uZ3MgdGhhdCBhcmUgZXhwbGljaXQgYXJlIGNsb3NlbHkgcmVsYXRlZCB0byBoZWF2eSBtZXRhbCBhbmQgZ3J1bmdlIHNvbmdzLgoyLiBEaXNuZXksIGphenosIGFuZCBjbGFzc2ljYWwtdG9uayBzb25ncyBhcmUgcHJvYmFibHkgaGlnaCBvbiB0aGUgaW5zdHJ1bWVudGFsIHNjYWxlLCB3aGlsZSBuZXctYWdlLCBhbWJpZW50LCBzbGVlcCBzb25ncyBhcmUgaGlnaCBvbiB0aGUgYWNvdXN0aWNuZXNzIHNjYWxlLgozLiBTZWVtcyBsaWtlIHRoZSBzbG93ZXIgc29uZ3MgKEdyYXZlLCBMZW50bywgTGFyZ2hldHRvLCBBZGFnaW8pIGFyZSBhbHNvIG9uIHRoZSByaWdodCBzaWRlIG9mIHRoZSBwbG90LCB3aGljaCBhcmUgbW9yZSBhY291c3RpYywgaW5zdHJ1bWVudGFsIHNvbmdzLiBXaGVyZWFzIHRoZSBmYXN0ZXIgc29uZ3MgYXJlIG9uIHRoZSBsZWZ0IHNpZGUuCgojIyBDb2xvcmluZyB0aGUgUENBIHBsb3QgdXNpbmcgY2F0ZWdvcmljYWwgdmFyaWFibGVzCgpXZSBjYW4gYWxzbyBwbG90IGFsbCB0aGUgaW5kaXZpZHVhbHMgaW4gUEMxIGFuZCBQQzIgYXMgYXhlcywgYW5kIGNvbG9yLWNvZGUgaXQgYnkgY2F0ZWdvcmljYWwgdmFyaWFibGVzLgpXZSdsbCBleGFtaW5lIG9uZSBjYXRlZ29yaWNhbCB2YXJpYWJsZTogRXhwbGljaXRuZXNzCgpgYGB7cn0KCiMgUFJPSkVDVElPTiBPRiBJTExVU1RSQVRJVkUgcXVhbGl0YXRpdmUgdmFyaWFibGVzIG9uIGluZGl2aWR1YWxzJyBtYXAKdmFyY2F0PWZhY3RvcihkZFssM10pCnBsb3QoUHNpWywxXSxQc2lbLDJdLGNvbD1jKCJncmV5IiwgInJlZCIpW3ZhcmNhdF0pCmF4aXMoc2lkZT0xLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iZGFya2dyYXkiKQpheGlzKHNpZGU9MywgcG9zPSAwLCBsYWJlbHMgPSBGLCBjb2w9ImRhcmtncmF5IikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJkYXJrZ3JheSIpCmF4aXMoc2lkZT00LCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iZGFya2dyYXkiKQpsZWdlbmQoImJvdHRvbWxlZnQiLGxldmVscyh2YXJjYXQpLHBjaD0xLGNvbD1jKCJncmV5IiwgInJlZCIpLCBjZXg9MC42KQoKCiMgT3ZlcnByb2plY3QgVEhFIENERyBPRiAgTEVWRUxTIE9GIHZhcmNhdApmZGljMSA9IHRhcHBseShQc2lbLDFdLHZhcmNhdCxtZWFuKQpmZGljMiA9IHRhcHBseShQc2lbLDJdLHZhcmNhdCxtZWFuKSAKCnRleHQoZmRpYzEsZmRpYzIsbGFiZWxzPWxldmVscyhmYWN0b3IodmFyY2F0KSksY29sPSJjeWFuIiwgY2V4PTAuNzUpCgpgYGAKCkFsdGhvdWdoIHRoZXJlIGFyZSBub3QgbWFueSBleHBsaWNpdCBzb25ncywgd2UgY2FuIHNlZSB0aGF0IHRoZSBleHBsaWNpdCBzb25ncyB0ZW5kIHRvIGJlIG9uIHRoZSBsZWZ0IHNpZGUgb2YgUEMxLgoKCmBgYHtyfQoKIyBQUk9KRUNUSU9OIE9GIElMTFVTVFJBVElWRSBxdWFsaXRhdGl2ZSB2YXJpYWJsZXMgb24gaW5kaXZpZHVhbHMnIG1hcAp2YXJjYXQ9ZmFjdG9yKGRkWywxOF0pCnBsb3QoUHNpWywxXSxQc2lbLDJdLGNvbD1yYWluYm93KDkpW3ZhcmNhdF0pCmF4aXMoc2lkZT0xLCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iZGFya2dyYXkiKQpheGlzKHNpZGU9MywgcG9zPSAwLCBsYWJlbHMgPSBGLCBjb2w9ImRhcmtncmF5IikKYXhpcyhzaWRlPTIsIHBvcz0gMCwgbGFiZWxzID0gRiwgY29sPSJkYXJrZ3JheSIpCmF4aXMoc2lkZT00LCBwb3M9IDAsIGxhYmVscyA9IEYsIGNvbD0iZGFya2dyYXkiKQpsZWdlbmQoImJvdHRvbWxlZnQiLGxldmVscyh2YXJjYXQpLHBjaD0xLGNvbD1yYWluYm93KDkpLCBjZXg9MC42KQoKCiMgT3ZlcnByb2plY3QgVEhFIENERyBPRiAgTEVWRUxTIE9GIHZhcmNhdApmZGljMSA9IHRhcHBseShQc2lbLDFdLHZhcmNhdCxtZWFuKQpmZGljMiA9IHRhcHBseShQc2lbLDJdLHZhcmNhdCxtZWFuKSAKCnRleHQoZmRpYzEsZmRpYzIsbGFiZWxzPWxldmVscyhmYWN0b3IodmFyY2F0KSksY29sPSJjeWFuIiwgY2V4PTAuNzUpCgpgYGAKCkZyb20gdGhlIHRlbXBvIGNhdGVnb3JpZXMgcGxvdCB3ZSBzZWUgdGhhdCB0aGUgbGVmdCBzaWRlIG9mIFBDQSBpcyB0aGUgZmFzdGVyIHNvbmdzLCBhbmQgdGhlIHJpZ2h0IHNpZGUgYXJlIHRoZSBzbG93ZXIgc29uZ3MuCg==